<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            完全背包完全平方数
            题目描述: 
                给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

                给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

                完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

                示例 1：

                输入：n = 12
                输出：3
                解释：12 = 4 + 4 + 4
                示例 2：

                输入：n = 13
                输出：2
                解释：13 = 4 + 9
        */


        /*
            动态规划解法:
            类型

            dp含义：dp[j] => 和为j的完全平方数的最小数量
            递推公式:
                递推公式1：必须把square先取出来，dp[j] = Math.min(dp[j], dp[j - square[i]] + 1)
                递推公式2：dp[j] = Math.min(dp[j], dp[j - i * i] + 1)
            初始化：
                dp[0]必须是0,构成0需要数字为0、
                其他初始化为Infinity
            遍历顺序：
                先遍历背包或者先遍历物品都可以
            举例：
                递推公式1和零钱兑换的方法一致；
                递推公式2：
                n = 5
                背包：0 1 2 3 4 5 => 1和4是完全平方数，最小数量就是2
                初始化
                dp = [0, Infinity, Infinity, Infinity, Infinity]
                i = 0
                dp[1] = Math.min(dp[1] + dp[1 - i * i => 1 - 0 * 0] + 1) = Math.min(dp[1], dp[1 - 0] + 1) = 1
                dp[2] = Math.min(dp[2] + dp[2 - i * i => 2 - 0 * 0] + 1) = Math.min(dp[2], dp[2 - 0] + 1) = 1
                dp[3] = Math.min(dp[3] + dp[3 - i * i => 3 - 0 * 0] + 1) = Math.min(dp[3], dp[3 - 0] + 1) = 1
                dp[4] = Math.min(dp[4] + dp[4 - i * i => 4 - 0 * 0] + 1) = Math.min(dp[4], dp[4 - 0] + 1) = 1
                dp[5] = Math.min(dp[5] + dp[5 - i * i => 5 - 0 * 0] + 1) = Math.min(dp[5], dp[5 - 0] + 1) = 1
                i = 1
                dp[1] = Math.min(dp[1] + dp[1 - i * i => 1 - 1 * 1] + 1) = Math.min(dp[1], dp[1 - 0] + 1) = 1
                dp[2] = Math.min(dp[2] + dp[2 - i * i => 2 - 1 * 1] + 1) = Math.min(dp[2], dp[2 - 1] + 1) = 2
                dp[3] = Math.min(dp[3] + dp[3 - i * i => 3 - 1 * 1] + 1) = Math.min(dp[3], dp[3 - 1] + 1) = 3
                dp[4] = Math.min(dp[4] + dp[4 - i * i => 4 - 1 * 1] + 1) = Math.min(dp[4], dp[4 - 1] + 1) = 4
                dp[5] = Math.min(dp[5] + dp[5 - i * i => 5 - 1 * 1] + 1) = Math.min(dp[5], dp[5 - 1] + 1) = 5

                i = 2
                dp[1] = Math.min(dp[1] + dp[1 - i * i => 1 - 2 * 2] + 1) = Math.min(dp[1], dp[1 - 4] + 1) = 1
                dp[2] = Math.min(dp[2] + dp[2 - i * i => 2 - 2 * 2] + 1) = Math.min(dp[2], dp[2 - 4] + 1) = 2
                dp[3] = Math.min(dp[3] + dp[3 - i * i => 3 - 2 * 2] + 1) = Math.min(dp[3], dp[3 - 4] + 1) = 3
                dp[4] = Math.min(dp[4] + dp[4 - i * i => 4 - 2 * 2] + 1) = Math.min(dp[4], dp[4 - 4] + 1) = 1
                dp[5] = Math.min(dp[5] + dp[5 - i * i => 5 - 2 * 2] + 1) = Math.min(dp[5], dp[5 - 4] + 1) = 2
        */


        /* 
            O(n * 根号n)
            O(n)
        */

        var numSquares = function(n) {
            if (n === 0) return 0
            let dp = new Array(n + 1).fill(Infinity)
            dp[0] = 0
            for (let i = 0; i * i <= n; i++) {
                for (let j = 1; j <= n; j++) {
                    if (j - i * i >= 0) {
                        dp[j] = Math.min(dp[j], dp[j - i * i] + 1)
                    }
                }
            }
            return dp[n]
        };
        console.log(numSquares(25));
        console.log(numSquares(2));
        console.log(numSquares(1));
    </script>
</body>

</html>